{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #魔术排列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #queue #array #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #队列 #数组 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isMagic"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #魔术排列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "秋日市集上，魔术师邀请小扣与他互动。魔术师的道具为分别写有数字 `1~N` 的 `N` 张卡牌，然后请小扣思考一个 `N` 张卡牌的排列 `target`。\n",
    "\n",
    "魔术师的目标是找到一个数字 k（k >= 1），使得初始排列顺序为 `1~N` 的卡牌经过特殊的洗牌方式最终变成小扣所想的排列 `target`，特殊的洗牌方式为：\n",
    "- 第一步，魔术师将当前位于 **偶数位置** 的卡牌（下标自 1 开始），保持 **当前排列顺序** 放在位于 **奇数位置** 的卡牌之前。例如：将当前排列 [1,2,3,4,5] 位于偶数位置的 [2,4] 置于奇数位置的 [1,3,5] 前，排列变为 [2,4,1,3,5]；\n",
    "- 第二步，若当前卡牌数量小于等于 `k`，则魔术师按排列顺序取走全部卡牌；若当前卡牌数量大于 `k`，则取走前 `k` 张卡牌，剩余卡牌继续重复这两个步骤，直至所有卡牌全部被取走；\n",
    "\n",
    "卡牌按照魔术师取走顺序构成的新排列为「魔术取数排列」，请返回是否存在这个数字 k 使得「魔术取数排列」恰好就是 `target`，从而让小扣感到大吃一惊。\n",
    "\n",
    "**示例 1：**\n",
    ">输入：`target = [2,4,3,1,5]`\n",
    ">\n",
    ">输出：`true`\n",
    ">\n",
    ">解释：排列 target 长度为 5，初始排列为：1,2,3,4,5。我们选择 k = 2：\n",
    ">第一次：将当前排列 [1,2,3,4,5] 位于偶数位置的 [2,4] 置于奇数位置的 [1,3,5] 前，排列变为 [2,4,1,3,5]。取走前 2 张卡牌 2,4，剩余 [1,3,5]；\n",
    ">第二次：将当前排列 [1,3,5] 位于偶数位置的 [3] 置于奇数位置的 [1,5] 前，排列变为 [3,1,5]。取走前 2 张 3,1，剩余 [5]；\n",
    ">第三次：当前排列为 [5]，全部取出。\n",
    ">最后，数字按照取出顺序构成的「魔术取数排列」2,4,3,1,5 恰好为 target。\n",
    "\n",
    "**示例 2：**\n",
    ">输入：`target = [5,4,3,2,1]`\n",
    ">\n",
    ">输出：`false`\n",
    ">\n",
    ">解释：无法找到一个数字 k 可以使「魔术取数排列」恰好为 target。\n",
    "\n",
    "\n",
    "**提示：**\n",
    "- `1 <= target.length = N <= 5000`\n",
    "- 题目保证 `target` 是 `1~N` 的一个排列。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [er94lq](https://leetcode.cn/problems/er94lq/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [er94lq](https://leetcode.cn/problems/er94lq/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,4,3,1,5]', '[5,4,3,2,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isMagic(self, target: List[int]) -> bool:\n",
    "        # 123456789\n",
    "        n = len(target)\n",
    "        l = [i+1 for i in range(n)]\n",
    "        l = l[1::2]+l[0::2]\n",
    "        idx = 0\n",
    "        while idx<n and l[idx]==target[idx]:\n",
    "            idx+=1\n",
    "        k=idx\n",
    "        # print(k)\n",
    "        right = l[idx:]\n",
    "        # print(right)\n",
    "        for _ in range(n):\n",
    "            idx0=0\n",
    "            l = right[1::2]+right[0::2]\n",
    "            if idx<n and idx+k>=n:\n",
    "                return target[idx:]==l\n",
    "            while idx<n and idx0<k and target[idx]==l[idx0]:\n",
    "                idx0+=1\n",
    "                idx+=1\n",
    "            right = l[idx0:]\n",
    "            # print(right)\n",
    "        return idx==n\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMagic(self, target: List[int]) -> bool:\n",
    "        N = len(target)\n",
    "        TL = list(range(1, N + 1))\n",
    "        TL = TL[1::2] + TL[::2]\n",
    "        k=0\n",
    "        while k<N and TL[k]== target[k]: \n",
    "            k += 1\n",
    "        if k==0:return False\n",
    "        elif k==N:return True\n",
    "        TL=TL[k:]\n",
    "        index=k\n",
    "        while len(TL) > 1:\n",
    "            n=len(TL)\n",
    "            TL = TL[1::2] + TL[::2]\n",
    "            tk=0\n",
    "            for tl in TL:\n",
    "                if tl != target[index+tk] or tk>=k: break\n",
    "                tk += 1\n",
    "            if min(k,n) != tk: return False\n",
    "            index+=tk\n",
    "            TL = TL[tk:]\n",
    "        return TL[0] == target[-1] if len(TL) == 1 else True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMagic(self, target: List[int]) -> bool:\n",
    "        n = len(target)\n",
    "        keys = list(range(1,n+1))\n",
    "        keys = keys[1::2]+keys[::2]\n",
    "        l = 0\n",
    "        for i in range(n):\n",
    "            if keys[i] == target[i]:\n",
    "                l += 1\n",
    "            else:\n",
    "                break\n",
    "        if l == 0: return False\n",
    "        i = l\n",
    "        while i < n:\n",
    "            k = min(l, n-i)\n",
    "            keys = keys[:i]+keys[i+1::2]+keys[i::2]\n",
    "            for j in range(i, i+k):\n",
    "                if keys[j] != target[j]:\n",
    "                    return False\n",
    "            i += k\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMagic(self, target: List[int]) -> bool:\n",
    "        N = len(target)\n",
    "        TL = list(range(1, N + 1))\n",
    "        TL = TL[1::2] + TL[::2]\n",
    "        k=0\n",
    "        while k<N and TL[k]== target[k]: \n",
    "            k += 1\n",
    "        if k==0:return False\n",
    "        elif k==N:return True\n",
    "        TL=TL[k:]\n",
    "        index=k\n",
    "        while len(TL) > 1:\n",
    "            n=len(TL)\n",
    "            TL = TL[1::2] + TL[::2]\n",
    "            tk=0\n",
    "            for tl in TL:\n",
    "                if tl != target[index+tk] or tk>=k: break\n",
    "                tk += 1\n",
    "            if min(k,n) != tk: return False\n",
    "            index+=tk\n",
    "            TL = TL[tk:]\n",
    "        return TL[0] == target[-1] if len(TL) == 1 else True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def isMagic(self, target: List[int]) -> bool:\n",
    "        n = len(target)\n",
    "        k = 0\n",
    "        while k < n:\n",
    "            if k < n // 2 and target[k] != (k+1)*2:\n",
    "                break\n",
    "            elif k >= n//2 and target[k] != (k - n//2) *2 + 1:\n",
    "                break\n",
    "            k += 1\n",
    "        if k == 0:\n",
    "            return False\n",
    "        if k == n:\n",
    "            return True\n",
    "        print(f\"k={k}\")\n",
    "        def gen():\n",
    "            nums = list(range(1, n+1))\n",
    "            tmp = [0]*n\n",
    "            nonlocal k\n",
    "            c = n\n",
    "            while c > 1:\n",
    "                idx = 0\n",
    "                count = 0\n",
    "                for i in range(1, c, 2):\n",
    "                    if count < k:\n",
    "                        yield nums[i]\n",
    "                        count += 1\n",
    "                    else:\n",
    "                        tmp[idx] = nums[i]\n",
    "                        idx += 1\n",
    "                for i in range(0, c, 2):\n",
    "                    if count < k:\n",
    "                        yield nums[i]\n",
    "                        count += 1\n",
    "                    else:\n",
    "                        tmp[idx] = nums[i]\n",
    "                        idx += 1\n",
    "                c -= k\n",
    "                nums, tmp = tmp, nums\n",
    "\n",
    "            if c == 1:\n",
    "                yield nums[0]\n",
    "        idx = 0\n",
    "        for n in gen():\n",
    "            if target[idx] != n:\n",
    "                return False\n",
    "            idx += 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shuffleCards(self, cards: List[int]) -> int:\n",
    "        '''洗牌过程'''\n",
    "        return cards[1::2] + cards[0::2]\n",
    "\n",
    "    def isMagic(self, target: List[int]) -> bool:\n",
    "        n = len(target)\n",
    "        cards = [i + 1 for i in range(n)]\n",
    "        cards = self.shuffleCards(cards)\n",
    "\n",
    "        # 根据第一次洗牌的结果，确定疑似 k 值\n",
    "        k = 0\n",
    "        while k < n:\n",
    "            if target[k] != cards[k]:\n",
    "                break\n",
    "            k += 1\n",
    "        if k == 0:\n",
    "            return False\n",
    "        \n",
    "        # 此后迭代的更新、遍历当前 cards 和 剩余的 target 数组，判断依次取出的数字是不是都相等\n",
    "        while cards:\n",
    "            for i in range(min(k, len(cards))):\n",
    "                if cards.pop(0) != target.pop(0):\n",
    "                    return False\n",
    "            cards = self.shuffleCards(cards)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isMagic(self, target: List[int]) -> bool:\n",
    "        k = 0                                       # 初始化k\n",
    "        le = len(target)\n",
    "        lst = [i for i in range(1, le + 1)]         # 初始化原列表\n",
    "        lst = lst[1::2] + lst[::2]                  # 偶位前置\n",
    "        for j in range(le):                         # 找到相同前缀\n",
    "            if target[j] == lst[j]:\n",
    "                k += 1\n",
    "            else:\n",
    "                break\n",
    "        if k == 0:\n",
    "            return False\n",
    "        res = []                                    # 存储最终结果\n",
    "        while le > k:                               # 开始变换\n",
    "            res.extend(lst[:k])                     # 取走前面K个数\n",
    "            target = target[k: ]                    # target保留后面部分作对比\n",
    "            lst = lst[k:]                           # lst的后面部分\n",
    "            lst = lst[1::2] + lst[::2]              # 转换\n",
    "            if target == lst:                       # 转换过程中进行判断\n",
    "                return True                         # 如果剩余的部分完全相同，则满足条件返回True\n",
    "            elif target[0] != lst[0]:               # 如果剩余部分没有公共前缀，则不满足后续条件，返回False\n",
    "                return False\n",
    "            le = len(lst)\n",
    "        res.extend(lst)\n",
    "        if res == target:\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMagic(self, target: List[int]) -> bool:\n",
    "        def shufflecards(cards):\n",
    "            return cards[1::2]+cards[0::2]\n",
    "        n=len(target)\n",
    "        cards=[i+1 for i in range(n)]\n",
    "        cards=shufflecards(cards)\n",
    "        k=0\n",
    "        while k<n:\n",
    "            if target[k]!=cards[k]:\n",
    "                break\n",
    "            k+=1\n",
    "        if k==0:\n",
    "            return False\n",
    "        while cards:\n",
    "            for i in range(min(k,len(cards))):\n",
    "                if cards.pop(0)!=target.pop(0):\n",
    "                    return False\n",
    "            cards=shufflecards(cards)\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMagic(self, target: List[int]) -> bool:\n",
    "        if len(target) == 1:\n",
    "            return True\n",
    "        simulate_list = []\n",
    "        lst = list(range(1, len(target) + 1))\n",
    "        lst = lst[1::2] + lst[::2]\n",
    "        k = 0\n",
    "        if target == lst:\n",
    "            return True\n",
    "        while target[k] == lst[k]:\n",
    "            k += 1\n",
    "        if k == 0:\n",
    "            return False\n",
    "        while len(lst) >= k:\n",
    "            simulate_list.extend(lst[:k])\n",
    "            lst = lst[k:]\n",
    "            lst = lst[1::2] + lst[::2]\n",
    "        if len(lst) > 0:\n",
    "            simulate_list.extend(lst)\n",
    "        return simulate_list == target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMagic(self, target: List[int]) -> bool:\n",
    "        li = [i + 1 for i in range(len(target))]\n",
    "\n",
    "        def bian(li):\n",
    "            ji = []\n",
    "            ou = []\n",
    "            for i in range(len(li)):\n",
    "                if i % 2 == 0:\n",
    "                    ou.append(li[i])\n",
    "                else:\n",
    "                    ji.append(li[i])\n",
    "            return ji+ou\n",
    "        temp = bian(li)\n",
    "        if target[0]!= temp[0]:\n",
    "            return False\n",
    "        for k in range(1, len(target)):\n",
    "            if target[k] != temp[k]:\n",
    "                break\n",
    "\n",
    "        ans = True\n",
    "        temp = li\n",
    "        while len(temp) > k:\n",
    "            new = bian(temp)\n",
    "            if new[:k] != target[:k]:\n",
    "                ans = False\n",
    "                break\n",
    "            else:\n",
    "                temp = new[k:]\n",
    "                target = target[k:]\n",
    "        if ans and bian(temp) == target:\n",
    "            return True\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMagic(self, target: List[int]) -> bool:\n",
    "        N = len(target)\n",
    "        TL = list(range(1, N + 1))\n",
    "        TL = TL[1::2] + TL[::2]\n",
    "        k=0\n",
    "        while k<N and TL[k]== target[k]: \n",
    "            k += 1\n",
    "        if k==0:return False\n",
    "        elif k==N:return True\n",
    "        TL=TL[k:]\n",
    "        index=k\n",
    "        while len(TL) > 1:\n",
    "            n=len(TL)\n",
    "            TL = TL[1::2] + TL[::2]\n",
    "            tk=0\n",
    "            for tl in TL:\n",
    "                if tl != target[index+tk] or tk>=k: break\n",
    "                tk += 1\n",
    "            if min(k,n) != tk: return False\n",
    "            index+=tk\n",
    "            TL = TL[tk:]\n",
    "        return TL[0] == target[-1] if len(TL) == 1 else True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef isMagic(self, target):\n",
    "\t\tn = len(target)\n",
    "\t\tori = list(range(1, n + 1))\n",
    "\t\tidx = 0\n",
    "\t\tk = 0\n",
    "\t\twhile idx < n:\n",
    "\t\t\tori = ori[1::2] + ori[::2]\n",
    "\t\t\tif k == 0:\n",
    "\t\t\t\twhile k < n and ori[k] == target[k]:\n",
    "\t\t\t\t\tk += 1\n",
    "\t\t\t\tif k == 0:\n",
    "\t\t\t\t\treturn False\n",
    "\t\t\telse:\n",
    "\t\t\t\tif ori[:k] != target[idx: idx + k]:\n",
    "\t\t\t\t\treturn False\n",
    "\t\t\tori = ori[k:]\n",
    "\t\t\tidx += k\n",
    "\t\treturn True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMagic(self, target: List[int]) -> bool:\n",
    "        n = len(target)\n",
    "        cardsdraw = []\n",
    "        abc = [i for i in range(1, n + 1)]\n",
    "        cardsleft = []\n",
    "        for k in range(1, n + 1):\n",
    "            cardsdraw = []\n",
    "            cardsleft = []\n",
    "            cardsleft = abc\n",
    "            while True:\n",
    "                cardsleft = cardsleft[1::2] + cardsleft[0::2]\n",
    "                cardsdraw += cardsleft[:k]\n",
    "                cardsleft = cardsleft[k:]\n",
    "                if cardsleft == []:\n",
    "                    break\n",
    "            if cardsdraw == target:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMagic(self, target: List[int]) -> bool:\n",
    "        N = len(target)\n",
    "        TL = list(range(1, N + 1))\n",
    "        TL = TL[1::2] + TL[::2]\n",
    "        k=0\n",
    "        while k<N and TL[k]== target[k]: \n",
    "            k += 1\n",
    "        if k==0:return False\n",
    "        elif k==N:return True\n",
    "        TL=TL[k:]\n",
    "        index=k\n",
    "        while len(TL) > 1:\n",
    "            n=len(TL)\n",
    "            TL = TL[1::2] + TL[::2]\n",
    "            tk=0\n",
    "            for tl in TL:\n",
    "                if tl != target[index+tk] or tk>=k: break\n",
    "                tk += 1\n",
    "            if min(k,n) != tk: return False\n",
    "            index+=tk\n",
    "            TL = TL[tk:]\n",
    "        return TL[0] == target[-1] if len(TL) == 1 else True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMagic(self, target: List[int]) -> bool:\n",
    "        n = len(target)\n",
    "        if n == 1:\n",
    "            return True \n",
    "        if target[0] != 2:\n",
    "            return False \n",
    "        cmp = [x for x in list(range(1, n + 1)) if x % 2 == 0] + [x for x in list(range(1, n + 1)) if x % 2 == 1]   \n",
    "        k = 0\n",
    "        for i in range(n):\n",
    "            if target[i] != cmp[i]:\n",
    "                k = i \n",
    "                break \n",
    "        if k == 0:\n",
    "            return True \n",
    "        cmp = cmp[k:]\n",
    "        target = target[k:]\n",
    "        while cmp:\n",
    "            cmp = cmp[1::2] + cmp[0::2]\n",
    "            if cmp[:k] != target[:k]:\n",
    "                return False\n",
    "            cmp = cmp[k:]\n",
    "            target = target[k:]\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def isMagic(self, target: List[int]) -> bool:\n",
    "        cards = [i + 1 for i in range(len(target))]\n",
    "        self.magicSort(cards, 0)\n",
    "        \n",
    "        maxk = self.sameCnt(cards, target, 0)\n",
    "        return (maxk != 0) and self.check(cards, target, maxk)\n",
    "\n",
    "    def check(self, cards: List[int], target: List[int], k: int) -> bool:\n",
    "        start = k\n",
    "        while start < len(cards) - 1:\n",
    "            self.magicSort(cards, start)\n",
    "            if self.sameCnt(cards, target, start) < k:\n",
    "                break\n",
    "            start += k\n",
    "        return self.sameCnt(cards, target, 0) == len(target)\n",
    "\n",
    "    def magicSort(self, v: List[int], start: int) -> None:\n",
    "        temp = []\n",
    "        temp.extend(v[:start])\n",
    "        temp.extend(v[start + 1::2])\n",
    "        temp.extend(v[start::2])\n",
    "        v.clear()\n",
    "        v.extend(temp)\n",
    "\n",
    "    def sameCnt(self, v: List[int], target: List[int], start: int) -> int:\n",
    "        for i in range(start, len(target)):\n",
    "            if v[i] != target[i]:\n",
    "                return i - start\n",
    "        return len(target) - start\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMagic(self, target: List[int]) -> bool:\n",
    "        origin = sorted(target)\n",
    "        k = 1\n",
    "        while k <= len(target):\n",
    "            start = origin[:]\n",
    "            result = []\n",
    "            while True:\n",
    "                odd = start[0::2]\n",
    "                even = start[1::2]\n",
    "                newlist = even + odd\n",
    "                if len(newlist) > k:\n",
    "                    result += newlist[:k]\n",
    "                    start = newlist[k:]\n",
    "                else:\n",
    "                    result += newlist\n",
    "                    break\n",
    "            if result == target:\n",
    "                return True\n",
    "            k += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMagic(self, target: List[int]) -> bool:\n",
    "        n = len(target)\n",
    "        cardsdraw = []\n",
    "        abc = [i for i in range(1, n + 1)]\n",
    "        cardsleft = []\n",
    "        for k in range(1, n + 1):\n",
    "            cardsdraw = []\n",
    "            cardsleft = []\n",
    "            cardsleft = abc\n",
    "            while True:\n",
    "                cardsleft = cardsleft[1::2] + cardsleft[0::2]\n",
    "                cardsdraw += cardsleft[:k]\n",
    "                cardsleft = cardsleft[k:]\n",
    "                if cardsleft == []:\n",
    "                    break\n",
    "            if cardsdraw == target:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMagic(self, target: List[int]) -> bool:\n",
    "        n=len(target)\n",
    "        A=[i for i in range(1,n+1)]\n",
    "        for k in range(1,n+1):\n",
    "            cardsdraw=[]\n",
    "            cardsleft=A\n",
    "            while True:\n",
    "                cardsleft=cardsleft[1::2]+cardsleft[::2]\n",
    "                cardsdraw+=cardsleft[:k]\n",
    "                cardsleft=cardsleft[k:]\n",
    "                if cardsleft==[]:\n",
    "                    break\n",
    "            if cardsdraw==target:\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMagic(self, target: list[int]) -> bool:\n",
    "        originalList = [i+1 for i in range(len(target))]\n",
    "        for k in range(1, len(target)+1):\n",
    "            finalList = self.getFinalList(originalList, k)\n",
    "            isSame = self.compare(target, finalList)\n",
    "            if isSame:\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "    def getFinalList(self, in_list: list[int], k: int) -> list[int]:\n",
    "        finalList = []\n",
    "        restList = in_list\n",
    "        while len(restList) > 0:\n",
    "            frontList = restList[1::2]\n",
    "            endList = restList[::2]\n",
    "            frontList.extend(endList)\n",
    "            finalList.extend(frontList[:k])\n",
    "            restList = frontList[k:]\n",
    "        finalList.extend(restList)\n",
    "        return finalList\n",
    "    \n",
    "    def compare(self, list0: list[int], list1: list[int]) -> bool:\n",
    "        if len(list0) != len(list1):\n",
    "            raise \"len(list0) != len(list1)\"\n",
    "        for i in range(len(list0)):\n",
    "            if list0[i] != list1[i]:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMagic(self, target: List[int]) -> bool:\n",
    "\n",
    "\n",
    "        def check(nums, target, k):\n",
    "            n = len(target)\n",
    "            nums = nums[1::2]+nums[::2]\n",
    "            if n <= k and nums == target:\n",
    "                return True\n",
    "            return nums[:k] == target[:k] and check(nums[k:], target[k:], k)\n",
    "\n",
    "        n = len(target)\n",
    "        for k in range(1, n+1):\n",
    "            if check(list(range(1,n+1)), target, k):\n",
    "                return True\n",
    "\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isMagic(self, target: List[int]) -> bool:\n",
    "        n = len(target)\n",
    "        nums = list(range(1,n+1))\n",
    "        left, right = [], []\n",
    "        for i in range(n):\n",
    "            if(i%2==0):\n",
    "                right.append(nums[i])\n",
    "            else:\n",
    "                left.append(nums[i])\n",
    "        nums = left + right\n",
    "        maxk = 0\n",
    "        for v1, v2 in zip(nums,target):\n",
    "            if(v1 == v2):\n",
    "                maxk += 1\n",
    "            else:\n",
    "                break\n",
    "        if(maxk == 0):\n",
    "            return False\n",
    "        if(maxk >= n-1):\n",
    "            return True\n",
    "        \n",
    "        def check(nums,x,path):\n",
    "            if(len(nums) == 0):\n",
    "                return target == path\n",
    "            left, right = [], []\n",
    "            for i in range(len(nums)):\n",
    "                if(i%2==0):\n",
    "                    right.append(nums[i])\n",
    "                else:\n",
    "                    left.append(nums[i])\n",
    "            nums = left + right\n",
    "            path += nums[:x]\n",
    "            if(target[:len(path)] != path):\n",
    "                return False\n",
    "            return check(nums[x:],x,path)\n",
    "        for k in range(maxk,0,-1):\n",
    "            if(check(list(range(1,n+1)),k,[])):\n",
    "                return True\n",
    "        return False\n",
    "            \n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
